﻿#define _CRT_SECURE_NO_WARNINGS 1

 #include <iostream>
 #include <vector>
 using namespace std;

 int main() 
 {
     //动态表示：dp[i][j]表示从前i个物品选择，体积小于等于j的最大价值
     //动态转移方程：不选择i物品，dp[i][j] = dp[i-1][j] 体积是j
                  //选择i物品，dp[i][j] = dp[i-1][j-v[i]] 体积要减去当前物品的体积 要判断j-v[i]是否大于0，比如j是1，而当前物品的体积是5，那么减去就是小于0，就是不存在
     //初始化：多开一行一列，当i=0时，即选择0个物品，不管体积是多少，值都是0
            //当j=0时，不管选什么物品，都无法存进去，所以值都是0
     //填表顺序：从左往右，从上到下
     //返回值：dp[n][V];

     //恰好装满
     //动态表示：dp[i][j]表示从前i个物品选择，体积等于j的最大价值
     //动态转移方程：不选择i物品，dp[i][j] = dp[i-1][j] 如果dp[i-1][j] != -1，前面的物品中不存在体积总和为j的物品，那么这里也是不满足，即为-1
     //             选择i物品，dp[i][j] = dp[i-1][j-v[i]] 要判断 dp[i-1][j-v[i]]不等于-1，即前i-1中，可能不存在体积总和为j-v[i]的物品
     //初始化：多开一行一列，当i=0时，选择0个物品，当体积为0时，值为0，当体积大于0时，值为-1，因为没有刚好满足当前的体积
     //                    当j=0时，即体积为0，选择的物品依然为0
     //填表顺序：从左往右，从上到下
     //返回值：dp[n][V]

     int n = 0,V = 0;
     cin >> n >> V;
     vector<vector<int>> vw(n,vector(2,0));
     for(int i = 0; i < n; ++i)
     {
         cin >> vw[i][0] >> vw[i][1];
     }

     vector<vector<int>> dp_noSatisfy(n+1,vector<int>(V+1,0));
     vector<vector<int>> dp_Satisfy(n+1,vector<int>(V+1,0));

     for(int i = 1; i < V + 1; ++i)
     {
         dp_Satisfy[0][i] = -1;
     }

     for(int i = 1; i < n + 1; ++i)
     {
         for(int j = 1; j < V + 1; ++j)
         {
             if(j - vw[i-1][0] >= 0)//可以存入当前物品
             {
                 dp_noSatisfy[i][j] = max(dp_noSatisfy[i-1][j],dp_noSatisfy[i-1][j-vw[i-1][0]] + vw[i-1][1]);
             }
             else
             {
                 dp_noSatisfy[i][j] = dp_noSatisfy[i-1][j];
             }
         }
     }

     for(int i = 1; i < n + 1; ++i)
     {
         for(int j = 1; j < V + 1; ++j)
         {
             if(j - vw[i-1][0] >= 0 && dp_Satisfy[i-1][j - vw[i-1][0]] != -1)
             {
                 dp_Satisfy[i][j] = max(dp_Satisfy[i-1][j],dp_Satisfy[i-1][j-vw[i-1][0]] + vw[i-1][1]);
             }
             else
             {
                 dp_Satisfy[i][j] = dp_Satisfy[i-1][j];
             }
         }
     }

     cout << dp_noSatisfy[n][V] << endl;;
     if(dp_Satisfy[n][V] == -1)
         cout << 0 << endl;
     else
         cout << dp_Satisfy[n][V] << endl;

     return 0;
 }


#include <iostream>
#include <vector>
using namespace std;

int main()
{

    //空间优化，滚动数组，填表顺序，从右往左
    //注意优化后，不要强行解释dp[i]代表的含义
    int n = 0, V = 0;
    cin >> n >> V;
    vector<vector<int>> vw(n, vector(2, 0));
    for (int i = 0; i < n; ++i)
    {
        cin >> vw[i][0] >> vw[i][1];
    }

    vector<int> dp_noSatisfy(V + 1, 0);
    vector<int> dp_Satisfy(V + 1, 0);

    for (int i = 1; i < V + 1; ++i)
    {
        dp_Satisfy[i] = -1;
    }

    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = V; j >= vw[i - 1][0]; --j)
        {
            dp_noSatisfy[j] = max(dp_noSatisfy[j], dp_noSatisfy[j - vw[i - 1][0]] + vw[i - 1][1]);
        }
    }

    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = V; j >= vw[i - 1][0]; --j)
        {
            if (dp_Satisfy[j - vw[i - 1][0]] != -1)
            {
                dp_Satisfy[j] = max(dp_Satisfy[j], dp_Satisfy[j - vw[i - 1][0]] + vw[i - 1][1]);
            }
        }
    }

    cout << dp_noSatisfy[V] << endl;;
    if (dp_Satisfy[V] == -1)
        cout << 0 << endl;
    else
        cout << dp_Satisfy[V] << endl;

    return 0;
}

/*
描述
你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为vi,价值为wi
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi和wi，表示第i个物品的体积和价值。1≤n,V,vi,wi≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1
输入：
3 5
2 10
4 5
1 4
输出：
14
9

说明：
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
*/

